package nowcode_alg_oj

import org.scalatest.FunSuite


class OJ2019_1Suite extends FunSuite {
  test("1st debug") {
    /*
1/5
[编程题]独立的牛牛
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

小牛牛为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。

一个人生活增加了许多花费: 牛牛每天必须吃一个水果并且需要每天支付x元的房屋租金。

当前牛牛手中已经有f个水果和d元钱,牛牛也能去商店购买一些水果,商店每个水果售卖p元。

牛牛为了表现他独立生活的能力,希望能独立生活的时间越长越好,牛牛希望你来帮他计算一下他最多能独立生活多少天。


输入描述:
输入包括一行,四个整数x, f, d, p(1 <= x,f,d,p <= 2 * 10^9),以空格分割

输出描述:
输出一个整数, 表示牛牛最多能独立生活多少天。

输入例子1:
3 5 100 10

输出例子1:
11
     */
    import java.io.{BufferedReader, ByteArrayInputStream, InputStreamReader}

    object Main {
      def main(args: Array[String]): Unit = {
        val input =
          """3 5 100 10
            |10 5 18 10
            |""".stripMargin
        val inputStream = new ByteArrayInputStream(input.getBytes())
        //    val inputStream = System.in
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        while (line != null) {
          val Array(x, f, d, p) = line.split(" ").map(_.toInt)

          if (d / x <= f)
            println(d / x)
          else
            println(f + scala.math.floor((d - f * x) / (p + x)).toInt)

          line = br.readLine()
        }
      }
    }


    Main.main(null)
  }

  test("1st") {
    /*
    1/5
[编程题]独立的牛牛
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

小牛牛为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。

一个人生活增加了许多花费: 牛牛每天必须吃一个水果并且需要每天支付x元的房屋租金。

当前牛牛手中已经有f个水果和d元钱,牛牛也能去商店购买一些水果,商店每个水果售卖p元。

牛牛为了表现他独立生活的能力,希望能独立生活的时间越长越好,牛牛希望你来帮他计算一下他最多能独立生活多少天。


输入描述:
输入包括一行,四个整数x, f, d, p(1 <= x,f,d,p <= 2 * 10^9),以空格分割

输出描述:
输出一个整数, 表示牛牛最多能独立生活多少天。

输入例子1:
3 5 100 10

输出例子1:
11
     */
    import java.io.{BufferedReader, InputStreamReader}

    object Main {
      def main(args: Array[String]): Unit = {
        val inputStream = System.in
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        while (line != null) {
          val Array(x, f, d, p) = line.split(" ").map(_.toInt)

          if (d / x <= f)
            println(d / x)
          else
            println(f + scala.math.floor((d - f * x) / (p + x)).toInt)

          line = br.readLine()
        }
      }
    }

  }

  test("2nd debug") {
    /*
2/5
[编程题]牛牛炒股票
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股，但必须是整数。

输出描述:
输出一个整数表示牛牛最多能赚的钱数。

输入例子1:
3 5
3 6
2 3
1 1

输出例子1:
4
     */
    import java.io.{BufferedReader, ByteArrayInputStream, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        val input =
          """3 10
            |3 5
            |4 7
            |2 3""".stripMargin
        val inputStream = new ByteArrayInputStream(input.getBytes())
        //        val inputStream = System.in

        // 根据当前资产求获得(最大收益, 最小化成本)的一组股票
        //
        // @param pricesAndEarn 成本和收益
        // @param money         资产
        // @return 花费, 收益
        //
        def findBestStock(pricesAndEarn: Array[(Int, Int)], money: Int): (Int, Int) = {
          if (pricesAndEarn.nonEmpty) {
            val (p, earn) = pricesAndEarn.maxBy { case (price, earn) => (money / price * earn, -money / price * price) }
            (money / p * p, money / p * earn)
          } else
            (0, 0)
        }

        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val Array(n, m) = line.split(" ")
        val stockCnt = n.toInt
        val money = m.toInt

        val stockCollect = mutable.ArrayBuilder.make[(Int, Int)]
        var i = 0
        line = br.readLine()
        while (line != null && i <= stockCnt) {
          val Array(p1, p2) = line.split(" ")
          stockCollect += (p1.toInt -> p2.toInt)
          i += 1
          line = br.readLine()
        }

        /* 在资产负担的起的范围内选股票, 先买能买到收益最大的, 直到买不到任何正收益的股票 */
        val priceWithEarn = stockCollect.result().map { case (p1, p2) => (p1, p2 - p1) }.filter(_._2 > 0)
        var earn = 0
        var mm = money

        var canFound = true
        while (canFound) {
          val (cost, earnings) = findBestStock(priceWithEarn, mm)
          if (earnings <= 0)
            canFound = false
          else {
            mm -= cost
            earn += earnings
          }
        }
        println(earn)
        stockCollect.clear()

      }
    }

    Main.main(null)
  }

  test("2nd") {
    /*
2/5
[编程题]牛牛炒股票
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股，但必须是整数。

输出描述:
输出一个整数表示牛牛最多能赚的钱数。

输入例子1:
3 5
3 6
2 3
1 1

输出例子1:
4
     */
    import java.io.{BufferedReader, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        val inputStream = System.in

        // 根据当前资产求获得最大收益的一组股票
        //
        // @param pricesAndEarn 成本和收益
        // @param money         资产
        // @return 花费, 收益
        //
        def findBestStock(pricesAndEarn: Array[(Int, Int)], money: Int): (Int, Int) = {
          if (pricesAndEarn.nonEmpty) {
            val (p, earn) = pricesAndEarn.maxBy { case (price, earn) => (money / price * earn, -money / price * price) }
            (money / p * p, money / p * earn)
          } else
            (0, 0)
        }

        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val Array(n, m) = line.split(" ")
        val stockCnt = n.toInt
        val money = m.toInt

        val stockCollect = mutable.ArrayBuilder.make[(Int, Int)]
        var i = 0
        line = br.readLine()
        while (line != null && i <= stockCnt) {
          val Array(p1, p2) = line.split(" ")
          stockCollect += (p1.toInt -> p2.toInt)
          i += 1
          line = br.readLine()
        }

        /* 在资产负担的起的范围内选股票, 先买能买到收益最大的, 直到买不到任何正收益的股票 */
        val priceWithEarn = stockCollect.result().map { case (p1, p2) => (p1, p2 - p1) }.filter(_._2 > 0)
        var earn = 0
        var mm = money

        var canFound = true
        while (canFound) {
          val (cost, earnings) = findBestStock(priceWithEarn, mm)
          if (earnings <= 0)
            canFound = false
          else {
            mm -= cost
            earn += earnings
          }
        }
        println(earn)
        stockCollect.clear()

      }
    }

  }

  test("2nd 2") {
    /*
2/5
[编程题]牛牛炒股票
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股，但必须是整数。

输出描述:
输出一个整数表示牛牛最多能赚的钱数。

输入例子1:
3 5
3 6
2 3
1 1

输出例子1:
4
     */
    import java.io.{BufferedReader, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        val inputStream = System.in

        // 根据当前资产求获得最大收益的一组股票
        //
        // @param pricesAndEarn 成本和收益
        // @param money         资产
        // @return 花费, 收益
        //
        def findBestStock(pricesAndEarn: Array[(Int, Int)], money: Int): (Int, Int) = {
          val (p, earn) = pricesAndEarn.maxBy { case (price, earn) => money / price * earn }
          (money / p * p, money / p * earn)
        }

        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val Array(n, m) = line.split(" ")
        val stockCnt = n.toInt
        val money = m.toInt

        val stockCollect = mutable.ArrayBuilder.make[(Int, Int)]
        var i = 0
        while (line != null && i <= stockCnt) {
          val Array(p1, p2) = line.split(" ")
          stockCollect += (p1.toInt -> p2.toInt)
          i += 1
          line = br.readLine()
        }

        /* 在资产负担的起的范围内选股票, 先买能买到收益最大的, 直到买不到任何正收益的股票 */
        val priceWithEarn = stockCollect.result().map { case (p1, p2) => (p1, p2 - p1) }
        var earn = 0
        var mm = money

        var canFound = true
        while (canFound) {
          val (cost, earnings) = findBestStock(priceWithEarn, mm)
          if (earnings <= 0)
            canFound = false
          else {
            mm -= cost
            earn += earnings
          }
        }
        println(earn)
        stockCollect.clear()

      }
    }

  }

  test("3rd debug") {
    /*
[编程题]牛牛取快递
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括四个正整数，
表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，
起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。
位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，
当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:
对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

输入例子1:
3 3 1 3
1 2 3
2 3 3
3 1 1

输出例子1:
7
     */

    import java.io.{BufferedReader, ByteArrayInputStream, InputStreamReader}
    import scala.collection.mutable
    import scala.collection.mutable.ArrayBuffer

    object Main {
      def main(args: Array[String]): Unit = {
        val input =
          """4 4 1 3
            |1 2 3
            |2 4 3
            |4 3 2
            |3 1 1""".stripMargin
        val inputStream = new ByteArrayInputStream(input.getBytes())
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val numLine = line.split(" ").map(_.toInt)
        // 表示位置个数N: 2<=N<=10000
        val N = numLine(0)
        // 道路条数M: 1<=M<=100000
        val M = numLine(1)
        // 起点位置编号S: 1<=S<=N
        val S = numLine(2)
        // 快递位置编号T: 1<=T<=N
        val T = numLine(3)

        val graph: mutable.Map[(Int, Int), Double] = scala.collection.mutable.Map.empty
        // 中转矩阵, 如果从i到j需要中转, 则进行记录, 用于求取路径: 本题其实用不到
        val transit: mutable.Map[(Int, Int), Int] = scala.collection.mutable.Map.empty

        def getDist(edges: mutable.Map[(Int, Int), Double], i: Int, j: Int) = {
          if (i == j)
            0
          else if (edges.contains((i, j)))
            edges((i, j))
          else
            Double.PositiveInfinity
        }

        line = br.readLine()
        var i = 0
        while (line != null && i < M) {
          val Array(s, e, d) = line.split(" ").map(_.toInt)
          graph += ((s -> e) -> d)
          i += 1

          line = br.readLine()
        }


        for (k <- 1 to N) {
          for (i <- 1 to N) {
            for (j <- 1 to N) {
                val oldDist = getDist(graph, i, j)
                val sumDist = getDist(graph, i, k) + getDist(graph, k, j)
                if (oldDist > sumDist && !sumDist.isInfinite) {
                  graph += ((i -> j) -> sumDist)
                  transit += ((i -> j) -> k)
                }
            }
          }
        }

        println((getDist(graph, S, T) + getDist(graph, T, S)).toInt)
        def printPath(transit: mutable.Map[(Int, Int), Int], i: Int, j: Int): ArrayBuffer[Int] = {
          if(transit.contains((i, j)))
            (printPath(transit, i, transit((i, j))) ++ printPath(transit, transit((i, j)), j)).distinct
          else
            ArrayBuffer(i, j)
        }
        println(printPath(transit, S, T).mkString("->"))
        println(printPath(transit, T, S).mkString("->"))

      }
    }


    Main.main(null)

  }

  test("3rd debug: Dijkstra") {
    /*
[编程题]牛牛取快递
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括四个正整数，
表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，
起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。
位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，
当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:
对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

输入例子1:
3 3 1 3
1 2 3
2 3 3
3 1 1

输出例子1:
7
     */

    import java.io.{BufferedReader, ByteArrayInputStream, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        def getDist(edges: mutable.Map[(Int, Int), Double], i: Int, j: Int): Double = {
          if (i == j)
            0
          else if (edges.contains((i, j)))
            edges((i, j))
          else
            Double.PositiveInfinity
        }

        def dijkstra(
                      edges: mutable.Map[(Int, Int), Double],
                      S: Int,
                      N: Int): (mutable.Map[(Int, Int), Double], mutable.Map[(Int, Int), Int]) = {
          val transit: mutable.Map[(Int, Int), Int] = scala.collection.mutable.Map.empty

          val SS = scala.collection.mutable.Set.empty[Int]
          SS.add(S)

          val TT = scala.collection.mutable.Set(Range(1, N + 1):_*)
          TT.remove(S)

          val dist: mutable.Map[Int, Double] = edges.filter{ case ((p1, _), _) => p1 == S}.map {
            case ((_, p2), v) => (p2, v)
          }
          for(i <- 1 to N) {
            if(!(dist contains i)) {
              dist += (i -> Double.PositiveInfinity)
            }
          }

          while (TT.nonEmpty) {
            val minId = TT.minBy(j => if(!(dist contains j)) Int.MaxValue else dist(j))

            if(dist.contains(minId)) {
              val distOfMinId = dist(minId)

              SS.add(minId)
              TT.remove(minId)

              // 松弛
              dist.foreach {
                case (k, d) =>
                  if(!SS.contains(k) && d > getDist(edges, minId, k) + distOfMinId) {
                    dist(k) = getDist(edges, minId, k) + distOfMinId
                    transit += ((S -> k) -> minId)
                  }
              }
            }

          }

          (dist.map{ case (k, d) => (S, k) -> d}, transit)
        }


        val input =
          """4 4 1 3
            |1 2 3
            |2 4 3
            |4 3 2
            |3 1 1""".stripMargin
        val inputStream = new ByteArrayInputStream(input.getBytes())
//        val inputStream = System.in
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val numLine = line.split(" ")
        // 表示位置个数N: 2<=N<=10000
        val N = numLine(0).toInt
        // 道路条数M: 1<=M<=100000
        val M = numLine(1).toInt
        // 起点位置编号S: 1<=S<=N
        val S = numLine(2).toInt
        // 快递位置编号T: 1<=T<=N
        val T = numLine(3).toInt

        val graph: mutable.Map[(Int, Int), Double] = scala.collection.mutable.Map.empty

        line = br.readLine()
        var i = 0
        while (line != null && i < M) {
          val Array(s, e, d) = line.split(" ").map(_.toInt)
          graph += ((s -> e) -> d)
          i += 1

          line = br.readLine()
        }

        val (d1, path1) = dijkstra(graph, S, N)
        val (d2, path2) = dijkstra(graph, T, N)

        println((d1(S, T) + d2(T, S)).toInt)
      }
    }

    Main.main(null)

  }

  test("3rd") {
    /*
[编程题]牛牛取快递
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括四个正整数，
表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，
起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。
位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，
当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:
对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

输入例子1:
3 3 1 3
1 2 3
2 3 3
3 1 1

输出例子1:
7
     */

    import java.io.{BufferedReader, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        val inputStream = System.in
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val numLine = line.split(" ").map(_.toInt)
        // 表示位置个数N: 2<=N<=10000
        val N = numLine(0)
        // 道路条数M: 1<=M<=100000
        val M = numLine(1)
        // 起点位置编号S: 1<=S<=N
        val S = numLine(2)
        // 快递位置编号T: 1<=T<=N
        val T = numLine(3)

        val graph: mutable.Map[(Int, Int), Double] = scala.collection.mutable.Map.empty
        // 中转矩阵, 如果从i到j需要中转, 则进行记录, 用于求取路径: 本题其实用不到
        val transit: mutable.Map[(Int, Int), Int] = scala.collection.mutable.Map.empty

        def getDist(edges: mutable.Map[(Int, Int), Double], i: Int, j: Int) = {
          if (i == j)
            0
          else if (edges.contains((i, j)))
            edges((i, j))
          else
            Double.PositiveInfinity
        }

        line = br.readLine()
        var i = 0
        while (line != null && i < M) {
          val Array(s, e, d) = line.split(" ").map(_.toInt)
          graph += ((s -> e) -> d)
          i += 1

          line = br.readLine()
        }


        for (k <- 1 to N) {
          for (i <- 1 to N) {
            for (j <- 1 to N) {
              val oldDist = getDist(graph, i, j)
              val sumDist = getDist(graph, i, k) + getDist(graph, k, j)
              if (oldDist > sumDist && !sumDist.isInfinite) {
                graph += ((i -> j) -> sumDist)
                transit += ((i -> j) -> k)
              }
            }
          }
        }

        println((getDist(graph, S, T) + getDist(graph, T, S)).toInt)
//        def printPath(transit: mutable.Map[(Int, Int), Int], i: Int, j: Int): ArrayBuffer[Int] = {
//          if(transit.contains((i, j)))
//            (printPath(transit, i, transit((i, j))) ++ printPath(transit, transit((i, j)), j)).distinct
//          else
//            ArrayBuffer(i, j)
//        }
//        println(printPath(transit, S, T).mkString("->"))
//        println(printPath(transit, T, S).mkString("->"))

      }
    }


  }


  test("3rd Dijkstra") {
    /*
[编程题]牛牛取快递
时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:
每个输入包含一个测试用例。
输入的第一行包括四个正整数，
表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，
起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。
位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，
当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:
对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

输入例子1:
3 3 1 3
1 2 3
2 3 3
3 1 1

输出例子1:
7
     */

    import java.io.{BufferedReader, InputStreamReader}
    import scala.collection.mutable

    object Main {
      def main(args: Array[String]): Unit = {
        def getDist(edges: mutable.Map[(Int, Int), Double], i: Int, j: Int): Double = {
          if (i == j)
            0
          else if (edges.contains((i, j)))
            edges((i, j))
          else
            Double.PositiveInfinity
        }

        def dijkstra(
                      edges: mutable.Map[(Int, Int), Double],
                      S: Int,
                      N: Int): (mutable.Map[(Int, Int), Double], mutable.Map[(Int, Int), Int]) = {
          val transit: mutable.Map[(Int, Int), Int] = scala.collection.mutable.Map.empty

          val SS = scala.collection.mutable.Set.empty[Int]
          SS.add(S)

          val TT = scala.collection.mutable.Set(Range(1, N + 1):_*)
          TT.remove(S)

          val dist: mutable.Map[Int, Double] = edges.filter{ case ((p1, _), _) => p1 == S}.map {
            case ((_, p2), v) => (p2, v)
          }
          for(i <- 1 to N) {
            if(!(dist contains i)) {
              dist += (i -> Double.PositiveInfinity)
            }
          }

          while (TT.nonEmpty) {
            val minId = TT.minBy(j => if(!(dist contains j)) Int.MaxValue else dist(j))

            if(dist.contains(minId)) {
              val distOfMinId = dist(minId)

              SS.add(minId)
              TT.remove(minId)

              // 松弛
              dist.foreach {
                case (k, d) =>
                  if(!SS.contains(k) && d > getDist(edges, minId, k) + distOfMinId) {
                    dist(k) = getDist(edges, minId, k) + distOfMinId
                    transit += ((S -> k) -> minId)
                  }
              }
            }

          }

          (dist.map{ case (k, d) => (S, k) -> d}, transit)
        }


        val inputStream = System.in
        val br = new BufferedReader(new InputStreamReader(inputStream))

        var line = br.readLine()
        val numLine = line.split(" ")
        // 表示位置个数N: 2<=N<=10000
        val N = numLine(0).toInt
        // 道路条数M: 1<=M<=100000
        val M = numLine(1).toInt
        // 起点位置编号S: 1<=S<=N
        val S = numLine(2).toInt
        // 快递位置编号T: 1<=T<=N
        val T = numLine(3).toInt

        val graph: mutable.Map[(Int, Int), Double] = scala.collection.mutable.Map.empty

        line = br.readLine()
        var i = 0
        while (line != null && i < M) {
          val Array(s, e, d) = line.split(" ").map(_.toInt)
          graph += ((s -> e) -> d)
          i += 1

          line = br.readLine()
        }

        val (d1, path1) = dijkstra(graph, S, N)
        val (d2, path2) = dijkstra(graph, T, N)

        println((d1(S, T) + d2(T, S)).toInt)
      }
    }

  }

}
